package com.likou;

public class q215 {

//    public int findKthLargest(int[] nums, int k) {
//
//        return quickselect(nums, 0, nums.length - 1, k);
//    }
//
//    private int quickselect(int[] nums, int left, int right, int k) {
//        if (left == right) {
//            return nums[left];
//        }
//
//        int partition = partition(nums, left, right);
//        if (partition == k) {
//            return nums[k];
//        }
//        if (partition < k) {
//            return quickselect(nums, partition + 1, right, k);
//        } else {
//            return quickselect(nums, left, partition - 1, k);
//        }
//    }
//
//    private int partition(int[] nums, int left, int right) {
//        // 随机基准位置
//        int pivot = nums[right];
//        int partition = left;
//        for (int i = left; i < right; i++) {
//            if (nums[i] < pivot) {
//                int temp = nums[i];
//                nums[i] = nums[partition];
//                nums[partition] = temp;
//                partition++;
//            }
//        }
//
//        int temp = nums[partition];
//        nums[partition] = pivot;
//        nums[right] = temp;
//
//        return partition;
//    }


    public int findKthLargest(int[] nums, int k) {
        heapSort(nums, k);

        return nums[nums.length - k];
    }

    // 堆排序（大根堆）
    private void heapSort(int[] arr, int k) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        int mark = 0;
        for (int i = n - 1; i >= 1; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            mark++;
            if (mark==k){
                return;
            }

            heapify(arr, i, 0);
        }

    }

    private void heapify(int[] arr, int n, int i) {
        int maxIndex = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[maxIndex]) {
            maxIndex = left;
        }
        if (right < n && arr[right] > arr[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex != i) {
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;

            heapify(arr, n, maxIndex);
        }

    }
}
